# author@bupt_kt
# date@08/23/2021
# 此算法为算法一的对偶形式，但实际运行时，由于事先进行的数据内积运算量过大，复杂度n方远大于原始算法的kn，故实际效果并不好

import numpy as np

##读取训练集数据
def input_data():
    data=[]
    label=[] ##创建标签数组，为每一项数据做标记
    file=open(r'Mnist/mnist_train.csv','r')
    for line in file.readlines():
        l=line.strip().split(',')
        if (int(l[0])>=5) :
            label.append(1)
        else :
            label.append(-1)
        data.append([int(num) for num in l[1:]])    ##这里的数据特指数据集中的x
    return data,label

##进行模型训练,这里采用的是感知机的对偶形式的算法，运用向量a
def training(data,label):
    ##初始化
    gram=[]  ##矩阵存放数据内积结果
    data=np.mat(data)  ##将数据集转化为矩阵，方便后续运算
    m,n=np.shape(data) ##获得数据集的行列数
    w=np.zeros((1,n)) ##w初始化为全0矩阵
    a=np.zeros((1,m)) ##初始化向量a
    b=0
    e=0.0001

    ##计算矩阵,对称矩阵可以优化计算,但是复杂度为n平方，过于复杂
    for i in range(m):
        gram.append([int(data[i]*num.T) for num in data[0:]])
        print(gram[i])

    ##训练模型
    while 1: ##当所有样本点都正确分类时退出
        error=False
        generation=0
        for i in range(m):
            y=label[i]
            yi=0
            for k in range(m):
                yi += a[k]*gram[k][i]+a[k]
            if y*yi <= 0:
                a[i] += e*y    ##用向量a来存储每次w,和b的更新,a的每一项代表模型在该对应数据点上更新的程度
                error = True
        print("%d generations"%(++generation))
        if not error:
            break

    w=a*data
    for k in range(m):
        b+=a[k]
    return w,b



def test(w,b): ##测试模型成功率
    file=open(r'Mnist/mnist_test.csv','r')
    error=0
    data=[]
    label=[]
    for lines in file.readlines():
        l=lines.strip().split(',')
        if int(l[0])>=5 :
            label.append(1)
        else :
            label.append(-1)
        data.append([int(num) for num in l[1:]])
    data=np.mat(data)
    m,n=np.shape(data)
    for i in range(m):
        y=label[i]
        x=data[i].T
        if y*(w*x+b)<=0 :
            error+=1
    print((m-error)/m)
    return

if __name__ == '__main__':
    data,label=input_data()
    w,b=training(data,label)
    test(w,b)